{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# AdaBoost\n",
    "In this tutorial, we'll build a stump classifier and apply the AdaBoost algorithm. Our goal is to transform a weak classifier into something useful. \n",
    "\n",
    "This lecture covers the first part of chapter 7 in Peter Harrington's book (Harrington, P. (2012). Machine Learning in Action. Shelter Island, NY: Manning) with some added commentary. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Imports\n",
    "Running the code below will be comprensive for the tutorial.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# base requirements \n",
    "from IPython.display import Image\n",
    "from IPython.display import display\n",
    "from datetime import *\n",
    "import json\n",
    "from copy import *\n",
    "from pprint import *\n",
    "import pandas as pd\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "import json\n",
    "import rpy2\n",
    "%load_ext rpy2.ipython\n",
    "%R require(\"ggplot2\")\n",
    "% matplotlib inline\n",
    "from ggplot import *\n",
    "randn = np.random.randn\n",
    "\n",
    "# optional\n",
    "import warnings\n",
    "warnings.filterwarnings('ignore')\n",
    "\n",
    "# tutorial requirements \n",
    "\n",
    "#bokeh - http://bokeh.pydata.org/en/latest/docs/installation.html \n",
    "from bokeh.io import output_notebook\n",
    "from bokeh.plotting import figure, output_file, show\n",
    "output_notebook() # inline graphs\n",
    "#import bokeh.sampledata # this download is commented out b/c it's optional\n",
    "# bokeh.sampledata.download() # this download is commented out b/c it's optional"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Functions\n",
    "We'll dump the major code base into this section."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def stumpClassify(dataMatrix,dimen,threshVal,threshIneq):#just classify the data\n",
    "    \"\"\"\n",
    "    Performs a threshold comparison to classify data.\n",
    "    Everything on one side of the threshold is thrown into class -1, \n",
    "    and everything on the other side is thrown into class +1.\n",
    "    \"\"\"\n",
    "    retArray = np.ones((np.shape(dataMatrix)[0],1))\n",
    "    #print \"retArray\"\n",
    "    #display(retArray)\n",
    "    if threshIneq == 'lt':\n",
    "        retArray[dataMatrix[:,dimen] <= threshVal] = -1.0\n",
    "    else:\n",
    "        retArray[dataMatrix[:,dimen] > threshVal] = 1.0\n",
    "    return retArray\n",
    "\n",
    "def buildStump(dataArr,classLabels,D):\n",
    "    \"\"\"\n",
    "    Iterates over all of the possible inputs to stumpClassify() and finds \n",
    "    the best decision stump for our dataset. Best here will be with respect \n",
    "    to the data weight vector D. \n",
    "    \"\"\"\n",
    "    dataMatrix = np.mat(dataArr); labelMat = np.mat(classLabels).T\n",
    "    #print \"dataMatrix:\"\n",
    "    #display(dataMatrix)\n",
    "    #print \"labelMat:\"\n",
    "    #display(labelMat)\n",
    "    m,n = np.shape(dataMatrix)\n",
    "    #print (\"m:{}, n:{}\".format(m,n))\n",
    "    numSteps = 10.0; bestStump = {}; bestClasEst = np.mat(np.zeros((m,1)))\n",
    "    #print \"bestClasEst:\"\n",
    "    #display(bestClasEst)\n",
    "    minError = np.inf #init error sum, to +infinity\n",
    "    #print \"minError:\"\n",
    "    #display(minError)\n",
    "    #The first one goes over all the features in our dataset. You’re \n",
    "    #  considering numeric values, and you calculate the minimum and \n",
    "    #  maximum to see how large your step size should be. \n",
    "    for i in range(n):#loop over all dimensions\n",
    "        rangeMin = dataMatrix[:,i].min(); rangeMax = dataMatrix[:,i].max();\n",
    "        stepSize = (rangeMax-rangeMin)/numSteps\n",
    "        #print \"stepSize:{}\".format(stepSize)\n",
    "        # The next for loops loop over these values.\n",
    "        for j in range(-1,int(numSteps)+1):#loop over all range in current dimension\n",
    "            #The last for loop toggles your inequality between greater than and less than\n",
    "            for inequal in ['lt', 'gt']: #go over less than and greater than\n",
    "                threshVal = (rangeMin + float(j) * stepSize) #value at which we make our decision to classify one way or another\n",
    "                predictedVals = stumpClassify(dataMatrix,i,threshVal,inequal) #returns labels for each element\n",
    "                errArr = np.mat(np.ones((m,1)))\n",
    "                errArr[predictedVals == labelMat] = 0\n",
    "                #print \"\\n\\nerrArr:\"\n",
    "                #display(errArr)\n",
    "                #display(D.T) \n",
    "                weightedError = D.T*errArr  #calc total error multiplied by D <---------D is constant in this function but  varied inside AdaBoost\n",
    "                #print \"weightedError:\"\n",
    "                #display(weightedError)\n",
    "                #####\n",
    "                ##### uncomment line below for 1st pass\n",
    "                #####\n",
    "                #print \"split: dim %d, thresh %.2f, thresh ineqal: %s, the weighted error is %.3f\" % (i, threshVal, inequal, weightedError)\n",
    "                if weightedError < minError: #finds thhe best stump\n",
    "                    minError = weightedError\n",
    "                    bestClasEst = predictedVals.copy()\n",
    "                    bestStump['feature'] = i+1\n",
    "                    bestStump['thresh'] = threshVal\n",
    "                    bestStump['ineq'] = inequal\n",
    "    return bestStump,minError,bestClasEst\n",
    "\n",
    "def alpha(error):\n",
    "    return float(0.5*np.log((1.0-error)/max(error,1e-16)))\n",
    "\n",
    "def adaBoostTrainDS(dataArr,classLabels,numIt=40):\n",
    "    \"\"\"\n",
    "    The implementation of AdaBoost. We get back a set of weak \\\n",
    "    classifiers and weights (the signs of which we use as labels).\n",
    "    \"\"\"\n",
    "    weakClassArr = []\n",
    "    m = np.shape(dataArr)[0]\n",
    "    D = np.mat(np.ones((m,1))/m) #init D to all weights being equal\n",
    "    aggClassEst = np.mat(np.zeros((m,1))) #init to zero\n",
    "    for i in range(numIt):\n",
    "        bestStump,error,classEst = buildStump(dataArr,classLabels,D)# note: D varies to improve the classifier\n",
    "        alpha = float(0.5*np.log((1.0-error)/max(error,1e-16)))#calc alpha; note: max(error,eps) accounts for error=0\n",
    "        bestStump['alpha'] = alpha  \n",
    "        weakClassArr.append(bestStump) #store Stump Params in Array\n",
    "        #print \"classEst: \",classEst.T\n",
    "        expon = np.multiply(-1*alpha*np.mat(classLabels).T,classEst) #exponent for D calc, notice that multiplying \\\n",
    "                                                                     #   np.mat(classLabels).T & classEst is for sign \\\n",
    "                                                                     #   that drives D values to 0 or 1 \n",
    "        D = np.multiply(D,np.exp(expon)) #Calc New D for next iteration\n",
    "        D = D/D.sum() # D.sum() normalizes the values as probabilities that all sum to 1\n",
    "        #calc training error of all classifiers, if this is 0 quit for loop early (use break)\n",
    "        aggClassEst += alpha*classEst # <----- the magic; this allows the signs (labels) to be pushed around\n",
    "        aggErrors = np.multiply(np.sign(aggClassEst) != np.mat(classLabels).T,np.ones((m,1))) # 1's when error\n",
    "        errorRate = aggErrors.sum()/m # percent error\n",
    "        print \"total error: \",errorRate\n",
    "        if errorRate == 0.0: break\n",
    "    return weakClassArr,aggClassEst\n",
    "\n",
    "def adaClassify(datToClass,classifierArr):\n",
    "    \"\"\"\n",
    "    Given an unknown datum, we label it from training data.\n",
    "    \"\"\"\n",
    "    dataMatrix = np.mat(datToClass)\n",
    "    m = np.shape(dataMatrix)[0]\n",
    "    #print \"m:{}\".format(m)\n",
    "    aggClassEst = np.mat(np.zeros((m,1))) # predicted values\n",
    "    #print \"initial aggClassEst:{}\".format(aggClassEst)\n",
    "    for i in range(len(classifierArr)):\n",
    "        classEst = stumpClassify(dataMatrix,classifierArr[i]['feature']-1\\\n",
    "                                 , classifierArr[i]['thresh']\\\n",
    "                                 , classifierArr[i]['ineq'])#call stump classify\n",
    "        aggClassEst += classifierArr[i]['alpha']*classEst\n",
    "        \n",
    "        print \"set{}:{}\".format(i,aggClassEst)\n",
    "    return np.sign(aggClassEst)\n",
    "\n",
    "def loadData():\n",
    "    \"\"\"\n",
    "    Loads sample dataset as arrays.\n",
    "    \"\"\"\n",
    "    datMat = np.array([[ 1. ,  2.1],\n",
    "[2., 1.1], [1.3, 1.], [1., 1.], [2., 1.]])\n",
    "    classLabels = np.array([1.0, 1.0, -1.0, -1.0, 1.0])\n",
    "    return datMat,classLabels\n",
    "\n",
    "def loadSimpData():\n",
    "    \"\"\"\n",
    "    Loads dataset as matrix.\n",
    "    \"\"\"\n",
    "    datMat = np.matrix([[ 1. ,  2.1],\n",
    "[2., 1.1], [1.3, 1.], [1., 1.], [2., 1.]])\n",
    "    classLabels = [1.0, 1.0, -1.0, -1.0, 1.0]\n",
    "    return datMat,classLabels\n",
    "\n",
    "def build_simple_bokeh_graph():\n",
    "    data,labels = loadData() \n",
    "    print \"data:\"\n",
    "    display(data)\n",
    "    print \"labels:\"\n",
    "    display(labels)\n",
    "    print \"Feature 1 data:\"\n",
    "    d1 = data[(labels==1)]\n",
    "    display(d1)\n",
    "    print \"Feature 2 data:\"\n",
    "    d2 = data[(labels==-1)]\n",
    "    display(d2)\n",
    "\n",
    "    ## set up Bokeh figure\n",
    "    p = figure(\n",
    "       tools=\"pan,box_zoom,reset,save\"\n",
    "        , title=\"Data: Two Features & Two Classes\"\n",
    "       #y_axis_type=\"log\", y_range=[0.001, 10**11]\n",
    "        , x_axis_label='Feature 1'\n",
    "        , y_axis_label='Feature 2'\n",
    "    )\n",
    "\n",
    "    ## add data to Bokeh figure\n",
    "    p.scatter(d1[:,0], d1[:,1], legend=\"class1\", fill_color=\"red\", size=20,marker=\"circle\")\n",
    "    p.scatter(d2[:,0], d2[:,1], legend=\"class2\", fill_color=\"blue\", size=20,marker=\"square\")\n",
    "\n",
    "    # display Bokeh figure\n",
    "    show(p)\n",
    "\n",
    "def run_stump():\n",
    "    # run stump classifier without adaboost\n",
    "    datMat,classLabels=loadSimpData()\n",
    "    print \"Data:\"\n",
    "    display(datMat)\n",
    "    D = np.mat( np.ones((5,1)) / 5 )\n",
    "    print \"initial D:\"\n",
    "    display(D)\n",
    "    numSteps = 10.0;\n",
    "    print \"TEST:\"\n",
    "    x,y,z=buildStump(datMat,classLabels,D) # note: D is constant here, but this is the value that we will vary with adaboost.\n",
    "    print \"\\n\\nRESTULS:\"\n",
    "    print \" bestStump:{}\".format(x)\n",
    "    print \" smallest error:{}\".format(y)\n",
    "    print \" predicted labels:\"\n",
    "    display(z)\n",
    "\n",
    "def graph_alpha():\n",
    "    # Create graph of alpha values\n",
    "    x = np.arange(0.01,1,0.01)\n",
    "    alpha_calc = np.vectorize(alpha)\n",
    "    y = alpha_calc(x)\n",
    "\n",
    "    ## Bokeh output inline\n",
    "    #output_notebook() \n",
    "\n",
    "    ## set up Bokeh figure\n",
    "    p = figure(\n",
    "       tools=\"pan,box_zoom,reset,save\"\n",
    "        , title=\"How are the classifiers scored?\"\n",
    "       #y_axis_type=\"log\", y_range=[0.001, 10**11]\n",
    "        , x_axis_label='Error'\n",
    "        , y_axis_label='Alpha'\n",
    "    )\n",
    "\n",
    "    ## add data to Bokeh figure\n",
    "    p.line(x, y, legend=\"alpha curve\", color=\"blue\", line_width=2)\n",
    "    # guide line\n",
    "    a = np.array([.5,.5])\n",
    "    b = np.array([-1,1])\n",
    "    p.line(a,b, legend=\"50% error\", color=\"red\",line_width = 1, alpha=0.6, line_dash=\"4 4\")\n",
    "\n",
    "    # display Bokeh figure\n",
    "    show(p)\n",
    "\n",
    "def simple_application():\n",
    "    datArr,labelArr=loadSimpData()\n",
    "\n",
    "    print \"Building training set.\"\n",
    "    classifierArr = adaBoostTrainDS(datArr,labelArr,30)\n",
    "\n",
    "    print \"\\nclassifierArr:\"\n",
    "    display(classifierArr[0])\n",
    "\n",
    "    print \"Classification of unknown point:\"\n",
    "    display(adaClassify([0, 0],classifierArr[0]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What is a decision stump?\n",
    "Decision trees typically create a path that uses several features to label a dataset. With a stump, we try to pick a single feature in a dataset and use it to label every element. Let's start with an example. We'll create some labeled data. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "build_simple_bokeh_graph()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Which individual feature best helps us classify this dataset? As you might note, we'll always have an error. As such, we could call this method a week classifier. \n",
    "\n",
    "Let's first see how to build a decision stump, test if any of values are less than or greater than the threshold value we’re testing, and then loop over a weighted version of the dataset to find the stump that yields the lowest error.  \n",
    "\n",
    "__One important distinction at this point is that we're using equal weights across all elements in the dataset.__  Late, we'll use the AdaBoost algorithm to change these weights to optimize the accuracy of the labels. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We now have the ability to choose which point on a specific continuous feature we'll use as the threshold value to label our data. Let's see which value and dimension are selected to choose the best stump.\n",
    "### Use stump classifier w/out AdaBoost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "run_stump()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implement AdaBoost\n",
    "After building our stump classifier, we'll try to improve it using AdaBoost. We're going to change one set of values: `D`, which is a vector of weights. We'll change `D` through an iterative process. This weight vector adjust for incorrect labels. So we'll change `D` by evaluating those labels that we classified incorrectly and increasing their weight while simultaneously decreasing the weight on those values that we classify correctly. Initially, all of these weights will be equal, but at each iteration we'll re-evaluate the weights to adjust for failure/success. Hence, each point in the dataset will receive a custom weight depending on how well we classified it in the last iteration. \n",
    "\n",
    "To calculate alpha, $\\alpha$, we then sum up the weighted errors for each stump. __In short, the vector `D` is varied per stump - each of which is scored with an alpha value.__ \n",
    "\n",
    "Before we move on to undersatand how adaboots uses the our sets of alpha values, let's look a little more deeply at what this score means.\n",
    "\n",
    "We calculate our error rate with \n",
    "\\begin{equation*}\n",
    "\\epsilon = \\frac{number\\ of\\ incorrectly\\ classified\\ examples}{total\\ number\\ of\\ examples}\\\\    \n",
    "\\end{equation*}\n",
    "These errors are multiplied by the weights and then the alpha value is calculated as follows:\n",
    "\\begin{equation*}\n",
    "\\alpha = \\frac{1}{2}ln(\\frac{1-\\epsilon}{\\epsilon})\n",
    "\\end{equation*}\n",
    "\n",
    "Let's look at a graph of alpha values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "graph_alpha()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###What we can learn from this graph?\n",
    "(see Chris McCormick's discussion https://chrisjmccormick.wordpress.com/2013/12/13/adaboost-tutorial/)\n",
    "\n",
    "1. The classifier weight grows exponentially as the error approaches 0. Better classifiers are given exponentially more weight.\n",
    "2. The classifier weight is zero if the error rate is 0.5. A classifier with 50% accuracy is no better than random guessing, so we ignore it.\n",
    "3. The classifier weight grows exponentially negative as the error approaches 1. We give a negative weight to classifiers with worse worse than 50% accuracy. “Whatever that classifier says, do the opposite!”.\n",
    "\n",
    "We end up using alpha through a series of iterations that drive the labeling error closer to zero. The way this works is that we sum together the product of alpha and each stump's predicted values, which provides a vector of floats whose signs indicate our labels. \n",
    "\n",
    "We now understand that alpha relates to the sum of errors and is in some way associated with how much to weight each stump. Now we just need to understand how alpha (\\alpha) relates to the individualized weights in vector `D`:\n",
    "\n",
    "Correctly predicted,\n",
    "\\begin{equation*}\n",
    "D_{i}^{(t+1)}= \\frac{D_{i}^{(t)}e^{-\\alpha}}{Sum(D)}\\\\    \n",
    "\\end{equation*}\n",
    "Incorrectly predicted,\n",
    "\\begin{equation*}\n",
    "D_{i}^{(t+1)}= \\frac{D_{i}^{(t)}e^{\\alpha}}{Sum(D)}\\\\    \n",
    "\\end{equation*}\n",
    "\n",
    "D is a probability distribution, so the sum of all the elements in D must be 1.0. \n",
    "\n",
    "Let's consider the entire AdaBoost process:\n",
    "<img src=\"imgs/adaboost_process.png\" width=\"80%\">\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Create a set of weak classifiers using AdaBoost\n",
    "In this section, we'll apply the AdaBoost algorithm to labeled data. As we evaluate each of the classifiers, we will score them with an alpha value. Finally, we sum the product of the predicted labels and alpha for each point to create a matrix of floats. Each value in this matrix has a sign, which should correspond to the correct lables if our error went to zero."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "datMat,classLabels=loadSimpData()\n",
    "adaBoostTrainDS(datMat,classLabels,9)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Application of AdaBoost\n",
    "With the code that we've already written, we have a list of weak classifiers and with their corresponding alpha scores:\n",
    "\n",
    "<pre>\n",
    "    [\n",
    "      {'alpha': 0.6931471805599453, 'feature': 1, 'ineq': 'lt', 'thresh': 1.3}\n",
    "    , {'alpha': 0.9729550745276565, 'feature': 2, 'ineq': 'lt', 'thresh': 1.0}\n",
    "    , {'alpha': 0.8958797346140273, 'feature': 1, 'ineq': 'lt', 'thresh': 0.9}\n",
    "    ]\n",
    "</pre>\n",
    "So we can reuse the threshold value of the corresponding features in each of these weak classifiers as a stump to label the unknown data. We'll recycle `stumpClassify()` with this training data, which means that we can rate classifier's lable using the previously assigned alpha value. See `adaClassify()`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "display(simple_application())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###Pros/Cons of AdaBoost\n",
    "(Pro/Con notes below borrowed from Eric Emer's [presentation](http://math.mit.edu/~rothvoss/18.304.3PM/Presentations/1-Eric-Boosting304FinalRpdf.pdf))\n",
    "Pros\n",
    "* Fast   \n",
    "* Simple and easy to program\n",
    "* No parameters to tune\n",
    "* No prior knowledge needed\n",
    "about weak learner\n",
    "* Provably effective given\n",
    "Weak Learning Assumption\n",
    "* versatile\n",
    "\n",
    "Cons\n",
    "* Weak classifiers too\n",
    "complex leads to\n",
    "overfitting.\n",
    "* Weak classifiers too weak\n",
    "can lead to low margins,\n",
    "and can also lead to\n",
    "overfitting.\n",
    "* From empirical evidence,\n",
    "AdaBoost is particularly\n",
    "vulnerable to uniform\n",
    "noise.\n",
    "\n",
    "## Summary\n",
    "###How does AdaBoost optimize weights?\n",
    "The data points that have been misclassified most by the previous weak classifier are pinpointed and become the focus for the next iteration. By pinpointed, we see these reguarly misclassified elements receiving a larger weight and associated larger error. \n",
    "###How does AdaBoost aggregate many weak classifiers into a single prediction?\n",
    "With the score (alpha value) applied to the prediction set for each classifier, we aggregate the scores by their index value. The aggregated vector provides an optimally weighted majority vote of weak classifiers! \n",
    "\n",
    "See Rober Schapire's [Explaining Adaboost](http://rob.schapire.net/papers/explaining-adaboost.pdf) for a good discussion on Adaboost."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Appendix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Random notes: \n",
    "Bagging\n",
    "* reshuffle your training data to create k different trainig sets and\n",
    "learn \n",
    "* Combine the k different classifiers by majority voting\n",
    "\n",
    "Boosting\n",
    "* Assign different weights to training samples in a “smart” way so\n",
    "that different classifiers pay more attention to different samples\n",
    "* Weighted majority voting, the weight of individual classifier is\n",
    "proportional to its accuracy\n",
    "* Ada-boost (1996) was influenced by bagging, and it is superior\n",
    "to bagging"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "### Non linearly separable example\n",
    "http://scikit-learn.org/stable/auto_examples/ensemble/plot_adaboost_twoclass.html"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "print(__doc__)\n",
    "\n",
    "# Author: Noel Dawe <noel.dawe@gmail.com>\n",
    "#\n",
    "# License: BSD 3 clause\n",
    "\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "from sklearn.ensemble import AdaBoostClassifier\n",
    "from sklearn.tree import DecisionTreeClassifier\n",
    "from sklearn.datasets import make_gaussian_quantiles\n",
    "\n",
    "\n",
    "# Construct dataset\n",
    "X1, y1 = make_gaussian_quantiles(cov=2.,\n",
    "                                 n_samples=200, n_features=2,\n",
    "                                 n_classes=2, random_state=1)\n",
    "X2, y2 = make_gaussian_quantiles(mean=(3, 3), cov=1.5,\n",
    "                                 n_samples=300, n_features=2,\n",
    "                                 n_classes=2, random_state=1)\n",
    "X = np.concatenate((X1, X2))\n",
    "y = np.concatenate((y1, - y2 + 1))\n",
    "\n",
    "# Create and fit an AdaBoosted decision tree\n",
    "bdt = AdaBoostClassifier(DecisionTreeClassifier(max_depth=1),\n",
    "                         algorithm=\"SAMME\",\n",
    "                         n_estimators=200)\n",
    "\n",
    "bdt.fit(X, y)\n",
    "\n",
    "plot_colors = \"br\"\n",
    "plot_step = 0.02\n",
    "class_names = \"AB\"\n",
    "\n",
    "plt.figure(figsize=(10, 5))\n",
    "\n",
    "# Plot the decision boundaries\n",
    "plt.subplot(121)\n",
    "x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1\n",
    "y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1\n",
    "xx, yy = np.meshgrid(np.arange(x_min, x_max, plot_step),\n",
    "                     np.arange(y_min, y_max, plot_step))\n",
    "\n",
    "Z = bdt.predict(np.c_[xx.ravel(), yy.ravel()])\n",
    "Z = Z.reshape(xx.shape)\n",
    "cs = plt.contourf(xx, yy, Z, cmap=plt.cm.Paired)\n",
    "plt.axis(\"tight\")\n",
    "\n",
    "# Plot the training points\n",
    "for i, n, c in zip(range(2), class_names, plot_colors):\n",
    "    idx = np.where(y == i)\n",
    "    plt.scatter(X[idx, 0], X[idx, 1],\n",
    "                c=c, cmap=plt.cm.Paired,\n",
    "                label=\"Class %s\" % n)\n",
    "plt.xlim(x_min, x_max)\n",
    "plt.ylim(y_min, y_max)\n",
    "plt.legend(loc='upper right')\n",
    "plt.xlabel('x')\n",
    "plt.ylabel('y')\n",
    "plt.title('Decision Boundary')\n",
    "\n",
    "# Plot the two-class decision scores\n",
    "twoclass_output = bdt.decision_function(X)\n",
    "plot_range = (twoclass_output.min(), twoclass_output.max())\n",
    "plt.subplot(122)\n",
    "for i, n, c in zip(range(2), class_names, plot_colors):\n",
    "    plt.hist(twoclass_output[y == i],\n",
    "             bins=10,\n",
    "             range=plot_range,\n",
    "             facecolor=c,\n",
    "             label='Class %s' % n,\n",
    "             alpha=.5)\n",
    "x1, x2, y1, y2 = plt.axis()\n",
    "plt.axis((x1, x2, y1, y2 * 1.2))\n",
    "plt.legend(loc='upper right')\n",
    "plt.ylabel('Samples')\n",
    "plt.xlabel('Score')\n",
    "plt.title('Decision Scores')\n",
    "\n",
    "plt.tight_layout()\n",
    "plt.subplots_adjust(wspace=0.35)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
